|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross- platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Pattern-avoiding permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
For a permutation π, the major index of π is the sum of all indices i such that πi > πi+1. In this thesis, we study the distribution of the major index over pattern-avoiding permutations of length n. We focus on the number Mm n (Π) of permutations of length n with major index m and avoiding the set of patterns Π. First, we are able to show that for a singleton set Π = {σ} other than some trivial cases, the values Mm n (Π) are monotonic in the sense that Mm n (Π) ≤ Mm n+1(Π). Our main result is a study of the asymptotic behaviour of Mm n (Π) as n goes to infinity. We prove that for every fixed m, Π and n large enough, Mm n (Π) is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns. 1
|
|
|
Enumeration of compositions with forbidden patterns
Dodova, Borjana ; Klazar, Martin (advisor) ; Jelínek, Vít (referee)
Enumeration of pattern avoiding compositions of numbers Abstract The aim of this work was to find some new results for 3-regular compositions, i.e., for those compositions which avoid the set of patterns {121, 212, 11}. Those compositions can be regarded as a generalization of Carlitz composition. Based on the generating function of compositions avoiding the set of patterns {121, 11} and {212, 11} we derive an upper bound for the coefficients of the power series of the generating function of 3-regular compositions. Using the theory of finite automata we derive its lower bound. We develop this result further by defining 3-block compositions. For the generating function of 3-regular compositions we prove a recursive ralation. Besides that we also compute the generating function of compositions avoiding the set of patterns {312, 321} whose parts are in the set [d]. In the last section we prove that the generating function of Carlitz compositions is transcendental.
|
guest ::
